import math
import matplotlib.pyplot as plt

class Loc():
    def __init__(self,x,y):
        self.x=x
        self.y=y

class Res():
    def __init__(self, k, v):
        self.k=k
        self.v=v

# 计算欧式距离
def OSdist(loc1,loc2):
    return math.sqrt(pow(loc1.x-loc2.x,2)+pow(loc1.y-loc2.y,2))

# 返回set的list
def getLs(k):
    r=[]
    for i in range(k):
        r.append(set())
    return r

# 判断两次聚类结果是否相同
def pd(last,now,K):
    for i in range(K):
        if last[i] not in now:
            return False
    return True

# 求Loc集合中的横纵坐标平均数
def getMean(data,s):
    Xsum,Ysum=0,0
    for i in s:
        Xsum+=data[i].x
        Ysum+=data[i].y
    return [Xsum/len(s),Ysum/len(s)]


# k-means通用算法
def k_means(K,data):# K为聚类中心个数，data为传入数据组，每个子单元格式为（x，y）
    # 排除异常情况
    if len(data)<K:
        return
    # 确定相应聚类中心
    k=[]
    for i in range(K):
        k.append(data[i])

    # 迭代计算其余各点到聚类中心的欧式距离并分簇，结果不变时结束迭代
    flag = True
    last=getLs(K)
    while (flag):
        # 初始化K个聚类list
        R=getLs(K)
        # 将data中的点重新聚类
        for i in range(len(data)):
            # 确定第i个坐标数据与哪个聚类中心距离最小并归入相应
            d=[]
            # 第j个聚类中心
            for j in range(K):
                d.append(OSdist(data[i],k[j]))
            now_k=d.index(min(d))
            R[now_k].add(i)
        # 检验本次聚类结果是否与上次一致
        if pd(last,R,K):
            return Res(k,R)
        else:
            # 更新聚类中心
            new_k=[]
            for i in range(K):
                [X,Y]=getMean(data,R[i])
                new_k.append(Loc(X,Y))
            k=new_k
            last=R


# 确定初始化数据集
x=[0,1,3,8,9,10]
y=[0,2,1,8,10,7]
data=[]
for i in range(len(x)):
    loc=Loc(x[i],y[i])
    data.append(loc)

# 调用k-means算法计算
res=k_means(2,data)
# 输出聚类中心坐标以及进行存储
X=[]
Y=[]
for i in range(len(res.k)):
    print('第',i+1,'个聚类中心坐标为：(',res.k[i].x,',',res.k[i].y,')')
    X.append(res.k[i].x)
    Y.append(res.k[i].y)
# 输出每个簇包含的坐标
v=res.v
for i in range(len(v)):
    print('第',i+1,'个簇包含的坐标有：')
    for j in v[i]:
        print('(',data[j].x,data[j].y,')')
# 画出散点图
# 添加原有坐标到散点图中
plt.scatter(x,y)
# 添加聚类中心坐标到散点图中
plt.scatter(X,Y)
# 展示散点图
plt.show()
